package cn.zhaoyuening.algorithms.linked;

/**
 * Created by Buynow on 2017/8/9.
 */
public class ReverseLinked {
    public static Node reverse(Node headNode, int from, int to) {
        //在头节点前放一个临时前置节点 编号0
        Node prevNode = new Node();
        prevNode.setNext(headNode);

        //from 的前节点 与 to的后节点
        Node pFromNode = null;
        Node nToNode = null;

        //链表长度
        int len = -1;
        Node tmpNode = prevNode;
        while (tmpNode != null) {
            len++;
            pFromNode = len == from-1?tmpNode:pFromNode;
            nToNode = len == to+1?tmpNode:nToNode;
            tmpNode = tmpNode.getNext();
        }

        if (len == 0||from<1||to>len) {
            return null;
        }

        Node fromNode = pFromNode.getNext();
        reverse2Node(fromNode,nToNode,pFromNode);
        fromNode.setNext(nToNode);

        return prevNode.getNext();

    }

    private static void reverse2Node(Node node1,Node nToNode,Node pFromNode) {
        if (node1 == null) {
            return;
        }
        Node next = node1.getNext();
        if (node1.getNext() == nToNode||node1.getNext()==null) {
            pFromNode.setNext(node1);
            return ;
        }
        next.setNext(node1);
        reverse2Node(next,nToNode,pFromNode);
    }

    public static void main(String[] args) {
        Node<Integer> headNode = new Node<>(1);
        headNode.setNext(new Node<>(2).setNext(new Node<>(3).setNext(new Node<>(4).setNext(new Node<>(5)))));
        headNode = reverse(headNode, 2, 4);
        printLinked(headNode);

    }

    public static void printLinked(Node node) {
        while (node != null) {
            System.out.print(node.getData()+" ");
            node = node.getNext();
        }
    }
}
